package me.project.offer;


import java.util.HashMap;
import java.util.Map;

/**
 * @author mbryce
 * @date 2018/7/1
 */
public class Solution07_2 {
    private Map<Integer, Integer> inOrderNumsIndexs = new HashMap<Integer, Integer>();

    public TreeNode reConstructBinaryTree(int[] pre, int[] in){
        for (int i = 0 , len = in.length; i < len ; i++) {
            inOrderNumsIndexs.put(in[i], i);
        }
        return reConstructBinaryTree(pre, 0, pre.length - 1, in, 0, in.length - 1);
    }
    private TreeNode reConstructBinaryTree(int[] pre, int preL, int preR, int[] in, int inL, int inR) {
        if (preL > preR)
            return null;
        TreeNode root = new TreeNode(pre[preL]);
        int inIndex = inOrderNumsIndexs.get(root.val);
        int leftTreeSize = inIndex - inL;
        root.left = reConstructBinaryTree(pre, preL + 1, preL + leftTreeSize, in, inL, inL + leftTreeSize - 1);
        root.right = reConstructBinaryTree(pre, preL + leftTreeSize + 1, preR, in, inL + leftTreeSize + 1, inR);
        return root;
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
}
